USPTO Patents Application 09915603

1/10

2/10

CALCULATE WEIGHTING
FUNCTION BASED ON
PATTERN r

ADJUST THRESHOLD

VALUE BASED ON
WEIGHTING FUNCTION
AND PATTERN r

FIG. 4A

3/10

CREATE A MAPPING
FROM INPUT STRING t TO
THE INPUT TYPE OF
FORMAT f

I

USE FORMAT TO FIND
CANDIDATE VALUES
ACROSS INPUT
MAPPING

MAP CANDIDATE
VALUES BACK TO
POSITION ON INPUT
STRING t

SELECTNEXT
CANDIDATE

USE PARTITIONED PRE-
AND POST-CONTEXT
FROM r ON SPAN
SURROUNDING THE
CANDIDATE WITH EDIT
DISTANCE MATRICES
AND WEIGHTING
FUNCTION TO FILTER AND
GENERATE A SCORE FOR
THE CANDIDATE

FIG. 4B

4/10

YES

FIND ALL
MATCHES OF K
ONt

CONSTRUCT A SET
OF SPANS TO
REPRESENT
INTERESTING
REGIONS ONt

FIG. 4C

NO

CONSTRUCTA
SPAN THAT
REPRESENTS THE
FULL LENGTH OF t

5/10

CREATE AN EDIT DISTANCE MATRIX
[PRE] USING THE PRE CONTEXT OF

PATTERN r AND A WEIGHTING
FUNCTION AND A SPAN OF INPUT

FIND ALL INDICATOR CELLS IN THE
MATRIX WHOSE EDIT DISTANCE IS
ABOVE A THRESHOLD

*

FILTER THE INDICATOR SET USING
INFORMATION ABOUT EXPECTED
VALUE TYPE

USE THE POSITIONS OF THE
INDICATORS TO CREATE A MINIMAL SET
OF NON-OVERLAPPING SPANS OF
INTERESTING REGIONS IN t

*

GIVEN AN INTERESTING SPAN,
CREATE AN EDIT DISTANCE MATRIX
[POST] USING THE POST CONTEXT
PATTERN OF rAND THE WEIGHTING
FUNCTION

FOR EACH INDICATOR CELL THAT IS

ABOVE THE THRESHOLD, TRACE
BACKWARD TO FIND AN ALIGNMENT
POSITION. RETAIN ONLY THE BEST
SCORING INDICATOR FOR EACH
AUGNMENT

FIG. 4D

6/10

©

DETERMINE MAXIMUM
EXTENT OF POTENTIAL VALUE
FROM POSITION OF NEXT
INDICATOR

LETi=
POSITION OF INDICATOR

/=/+/

FIG. 4E

7/10

©

THE RESULT OF THE PARTITIONED CONTEXT
MATCHING SYSTEM IS A SET OF
CANDIDATE MATCHES WHERE EACH
MATCH CONTAINS A VALUE EXTRACTED
FROM THE VALUE WINDOW BETWEEN A
BEGIN INDICATOR OFFSET AND AN END

AUGNMENT OFFSET THE MATCH IS
ASSIGNED A SCORE BASED UPON THE
EDIT DISTANCE OF ITS PRE- AND POST-
CONTEXT PATTERNS IN ADDITION TO
SPECIAL (OPTIONAL) SCORING OF THE
VALUE ITSELF.

FIG. 4F

8/10

1
I

I

T — .

CM

CM

1
1

lo

1

CM

oo

1
1

io
I

CM

CM

oo

I

1

1 —

I

I

1

I —

I

iO
1

CM

1

i

^ —

CM

oo

I

les
i

^ —

CM

oo

1

1

i

u

i

1

(O
L_

CS

T —

CM

i

u,

Y-*

CM

oo

|CS
L

cs

i —

cm

CM

1
1

I
1
1

C\J

CM

I

1

jo

1

1

1

CM

oo

1

1
1

CM

/

f

i Q

C\.l

™

%

r
1

CM

r

io
1

CM

oo

oo

r~

t

Y — •

CM

1 —

! Q

1 —

cs

Y— »

CM

1 —

1 —

1 — .

CM

oo

CM

4 .

-f

Y*» .

CM

oo

!-

I —

Y-—

CVJ

CM

!-

CM

CM

/

|o

CM

oo

res

T^-

CM

CM

)C>

1 —

CM

/

CM

ICS

1 —

CM

oo

IS

Y"^

eg

CM

r-

Y~*

?

CM

oo

IS

Y~-

CM

oo

oo

r°-

r?

CM

oo

!-

CM

CM

CM

y~->

P

i?

CM

oo

!°

^

CM

T — .

CM

1
I

1

L

T

Y-^

i

jo
1

L..„

CM

Co

i

ICS

L

Y— «

T — .

CM

oo

I

! Q

1 —

-i

CM

1

i°

1 —

Y-—

CM

oo

I

!°

cs

Y— -

CM

oo

1

1 —
1

[

to

1

1

Y~-<.

Cr>

1

ICS

1

1

Y»^

CM

oo

1

ICS
I

1

Y— -

CM

oo

1 —
1

ICs
I

1 —

1 —

CM

oo

1 —
1

ICS
1

|

Y—

CM

oo

1 —
1

ICS

1

1 —

Y-~

CM

oo

1

1

ICS

1

1

— ■

CM

CM

1
1

ICS

1

T — ■

CM

oo

1
1

ICS

1

1

Y-—

CM

oo

CM

Y-»

!?

I
1
1
1

1

1 —

CM

i
i

!^

1

1
1
1
1

1

1
1

I

1
1

L_

1
1

1

1

jo
1 —

CS

CM

1

1 —

1

! Q

1 —

jo

CM

00

!<=>

v 3:

■ OS
OS

V

crs

9/10

INPUT

1 1 1

23 !

22

r

REPLACE \ 0fl ™

— V+-

"I

INSERT
21 '

20

FIG. 6

10/10

1
1

to
1
1

A

s

— i

Uj to

& !
a

1 — L

V I

CO
OS

CO f

CO K

a r

a h

v i

^9-

1^

3 !?

A

s

V |o

i
i

to

I

L

3

to

I

l

to

co !

to

§ !<=>

A

B

V

1

!<=>

CM

eg

oo

eg

oo

T —

eg

eg
/—

eg

/

/

1 —

$

a

eg

oo

eg

oo

rv i

<\i

oo

oo

<M

eg

eg

r\ i

i

t

eg

oo

O

eg

oo

t — .

eg

oo

i —

eg

oo

eg

oo

a^

V

eo